package com.itheima.algorithm.heap;

import java.util.Arrays;
import java.util.logging.Level;

/**
 * @author: TylerZhong
 * @description: 数据流的中位数
 */
public class E04Leetcode295 {

    private Heap left = new Heap(10, true);
    private Heap right = new Heap(10, false);

    /**
     * 两边数据一致，左右各取堆顶元素求平均
     * 左边多一个，取左边堆顶元素
     * @return
     */
    public double findMedia() {
        if (right.size == left.size) {
            return (right.peek() + left.peek()) / 2.0;
        } else {
            return left.peek();
        }
    }

    /**
     * 为了保证两边数据量的平衡
     *  两边个数一样时，左边个数加一
     *  两个个数不一样时，右边个数加一
     *
     * 但是，随便一个数能直接加入吗？
     *  左边个数加一时，应该挑右边最小的加入
     *  右边个数加一时，应该挑左边最大的加入
     * @param value
     */
    public void addNum(int value) {
        if (left.size == right.size) {
            right.offer(value);
            left.offer(right.poll());
        } else {
            left.offer(value);
            right.offer(left.poll());
        }
    }

    public static void main(String[] args) {
        Heap heap = new Heap(5, true);
        for (int i = 1; i <= 11; i++) {
            heap.offer(i);
            System.out.println(Arrays.toString(heap.array));
        }
    }

    public void test1() {
        E04Leetcode295 test = new E04Leetcode295();
        test.addNum(1);
        test.addNum(2);
        test.addNum(3);
        test.addNum(7);
        test.addNum(8);
        test.addNum(9);
        System.out.println(test);
        System.out.println(test.findMedia());
        test.addNum(10);
        System.out.println(test);
        System.out.println(test.findMedia());
        test.addNum(4);
        System.out.println(test);
        System.out.println(test.findMedia());
    }

    @Override
    public String toString() {
        return left.toString() + "<=>" + right.toString();
    }
}
